package gitdemo1.git3.pojo;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

public class Tree {
    public  Tree left;
    public  Tree right;
    public  int val;

    public Tree() {
    }

    public Tree(int val,Tree left, Tree right ) {
        this.left = left;
        this.right = right;
        this.val = val;
    }

    public static void main(String[] args) {
        Tree node7 =new Tree(7,null,null);
        Tree node6 =new Tree(6,null,null);
        Tree node5 =new Tree(5,node6,node7);
        Tree node4 =new Tree(4,null,null);
        Tree node3 =new Tree(3,null,null);
        Tree node2 =new Tree(2,node4,node5);
        Tree node1 =new Tree(1,node2,node3);
        miopre(node1);
    }

    public static void preorder(Tree root){
        if(root!=null){
            Stack<Tree> stack = new Stack<>();
            stack.add(root);
            while(!stack.isEmpty()){
                Tree node = stack.pop();
                System.out.println(node.val);
                if(node.right!=null){
                    stack.add(node.right);
                }
                if(node.left!=null){
                    stack.add(node.left);
                }
            }
        }
    }
    public static void levelorder(Tree root){
        Queue<Tree> q = new LinkedList<>();
        q.add(root);
        while(!q.isEmpty()){
            Tree node = q.poll();
            if (node!=null) {
                System.out.println(node.val);
                q.add(node.left);
                q.add(node.right);
            }
        }

    }

    public static void miopre(Tree cur){
        Tree mostRight=null;
        while(cur!=null){
            mostRight=cur.left;
            if(mostRight!=null){
                while (mostRight.right!=null&&mostRight.right!=cur){
                    mostRight=mostRight.right;
                }
                if(mostRight.right==null){
                    mostRight.right=cur;
                    System.out.println(cur.val);
                    cur=cur.left;
                    continue;
                }else {
                    mostRight.right=null;
                }
            }else {
                System.out.println(cur.val);
            }
            cur=cur.right;
        }

    }

    public static void miomide(Tree cur){
        Tree mostRight=null;
        while(cur!=null){
            mostRight=cur.left;
            if(mostRight!=null){
                while (mostRight.right!=null&&mostRight.right!=cur){
                    mostRight=mostRight.right;
                }
                if(mostRight.right==null){
                    mostRight.right=cur;
//                    System.out.println(cur.val);
                    cur=cur.left;
                    continue;
                }else {
                    mostRight.right=null;
                }
            }else {
//                System.out.println(cur.val);
            }
            System.out.println(cur.val);
            cur=cur.right;
        }

    }






}
